P6825 「EZEC-4」求和

$\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j}$

$\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]d^{i+j}$

$\sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor } [\gcd(i,j)=1]d^{(i+j)d}$

$\sum_{d=1}^n \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor }\sum_{j=1}^{\lfloor \frac{n}{dt} \rfloor } d^{(i+j)dt}$

$\sum_{d=1}^n \sum_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) (\sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor } d^{idt})^2$

计算等比数列和时，需要递归计算。

#include <cstdio>

const int MAXN = 1.5e6; int Mod;

int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { if( x < 0 ) x += Mod; if( y < 0 ) y += Mod; return 1ll * x * y % Mod; }
int Squ( int x ) { return Mul( x , x ); }
int Quick_pow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = Squ( x ) ) if( po & 1 ) p = Mul( p , x ); return p; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return Mul( x , Inv( y ) ); }

int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve() {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) prime[ ++ prnum ] = i , mu[ i ] = -1;
		for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
}

int Sum( int a1 , int q , int n ) { //首项为a1,公比为q，项数为n
	if( n == 1 ) return a1;
	int haf = Sum( a1 , q , n / 2 ) , amid = Quick_pow( q , n / 2 );
	return Add( Mul( haf , amid + 1 ) , n & 1 ? Quick_pow( q , n ) : 0 );
}
int Solve( int n ) {
	int Ans = 0;
	for( int d = 1 ; d <= n ; d ++ ) {
		int q1 = Quick_pow( d , d );
		for( int j = 1 , q = q1 ; j <= n / d ; j ++ , q = Mul( q , q1 ) ) {
			if( d == 1 )
				Ans = Add( Ans , Mul( mu[ j ] , Squ( n / d / j ) ) );
			else
				Ans = Add( Ans , Mul( mu[ j ] , Squ( Sum( q , q , n / d / j ) ) ) );
		}
	}
	return ( Ans + Mod ) % Mod;
}

int T , n;
signed main( ) {
	sieve();
	scanf("%d",&T);
	while( T -- ) {
		scanf("%d %d",&n,&Mod);
		printf("%d\n", Solve( n ) );
	}
	return 0;
}

顺带一提，似乎式子可以继续化简，但不好计算。

$\sum_{T=1}^n \sum_{d|T} d^T \mu(\frac{T}{d}) (\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor }d^{i})^2$

$\sum_{T=1}^n \left( \sum_{d|T} d^T \mu(\frac{T}{d})(\frac{1-d^{\lfloor \frac{T}{d} \rfloor}}{1-d})^2 \right)$